package com.yangzhe.algorithm.c038;

import java.util.Stack;

// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
public class Code06_SortStackWithRecursive {

    /**
     * 栈顶到栈底从小到大
     * 思路，过程相当于插入排序，但是有一个计数的优化
     * 1. 变量deep记录还未排序的栈深度，初始值就是整个栈的深度
     * 2. 从栈顶到deep找出当前栈中最大的数字stackMax
     * 3. 从栈顶到deep找出最大数字的个数maxCount
     * 4. 将最大的数字沉到栈底
     * 5. 此时未排序的个数 = deep - maxCount
     * <p>
     * 时间复杂度 O(n ^ 2) 空间复杂度 O(n)
     *
     * @param stack
     */
    public static void sort(Stack<Integer> stack) {
        int deep = getStackDeep(stack);
        while (deep > 0) {
            int stackMax = getStackMax(stack, deep);
            int maxCount = getMaxCount(stack, deep, stackMax);

            downMaxValue(stack, deep, stackMax, maxCount);

            deep = deep - maxCount;
        }
    }

    /**
     * 递归获取栈的深度
     *
     * @param stack 栈
     * @return
     */
    public static int getStackDeep(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return 0;
        } else {
            Integer pop = stack.pop();
            int stackDeep = getStackDeep(stack);

            // 恢复栈
            stack.push(pop);

            return stackDeep + 1;
        }
    }

    /**
     * 从栈顶到deep找到其中最大值
     *
     * @param stack 栈
     * @param deep  深度
     * @return 最大值
     */
    public static int getStackMax(Stack<Integer> stack, int deep) {
        if (deep == 0) {
            return Integer.MIN_VALUE;
        } else {
            Integer current = stack.pop();
            int stackMax = getStackMax(stack, deep - 1);

            // 恢复栈
            stack.push(current);

            return Math.max(stackMax, current);
        }
    }

    /**
     * 从栈顶到deep找到最大元素的个数
     *
     * @param stack 栈
     * @param deep  深度
     * @param max   最大元素
     * @return 最大元素个数
     */
    public static int getMaxCount(Stack<Integer> stack, int deep, int max) {
        if (deep == 0) {
            return 0;
        } else {
            Integer current = stack.pop();
            int maxCount = getMaxCount(stack, deep - 1, max);
            if (current == max) {
                maxCount++;
            }
            stack.push(current);
            return maxCount;
        }
    }

    /**
     * 从栈顶到deep把最大的数字按个数放在栈底
     *
     * @param stack    栈
     * @param deep     深度
     * @param max      最大元素
     * @param maxCount 最大元素个数
     */
    public static void downMaxValue(Stack<Integer> stack, int deep, int max, int maxCount) {
        if (deep == 0) {
            // 把最大的元素按个数放到底部
            while (maxCount > 0) {
                stack.push(max);
                maxCount--;
            }
        } else {
            Integer current = stack.pop();
            downMaxValue(stack, deep - 1, max, maxCount);

            // 其他元素按次序归位
            if (current != max) {
                stack.push(current);
            }
        }
    }

    // 为了测试
    // 生成随机栈
    public static Stack<Integer> randomStack(int n, int v) {
        Stack<Integer> ans = new Stack<Integer>();
        for (int i = 0; i < n; i++) {
            ans.add((int) (Math.random() * v));
        }
        return ans;
    }

    // 为了测试
    // 检测栈是不是从顶到底依次有序
    public static boolean isSorted(Stack<Integer> stack) {
        int step = Integer.MIN_VALUE;
        while (!stack.isEmpty()) {
            if (step > stack.peek()) {
                return false;
            }
            step = stack.pop();
        }
        return true;
    }

    // 为了测试
    public static void main(String[] args) {
        Stack<Integer> test = new Stack<Integer>();
        test.add(1);
        test.add(5);
        test.add(4);
        test.add(5);
        test.add(3);
        test.add(2);
        test.add(3);
        test.add(1);
        test.add(4);
        test.add(2);
        sort(test);
        while (!test.isEmpty()) {
            System.out.println(test.pop());
        }

        // 随机测试
        int N = 20;
        int V = 20;
        int testTimes = 20000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int n = (int) (Math.random() * N);
            Stack<Integer> stack = randomStack(n, V);
            sort(stack);
            if (!isSorted(stack)) {
                System.out.println("出错了!");
                break;
            }
        }
        System.out.println("测试结束");
    }

}
